package problems.daily.y2022m7;

import utils.beans.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 1161. 最大层内元素和
 * https://leetcode.cn/problems/maximum-level-sum-of-a-binary-tree/
 * @author habitplus
 * @since 2022/7/31 8:23
 */
public class D20220731_1161 {
    private final List<Integer> levelSum = new ArrayList<>();
    public int maxLevelSum(TreeNode root) {
        dfs(root, 0);

        int minIndex = 0;
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < levelSum.size(); i++) {
            if (levelSum.get(i) > maxSum) {
                maxSum = levelSum.get(i);
                minIndex = i;
            }
        }
        return minIndex + 1;
    }

    private void dfs(TreeNode root, int level) {
        if (root == null) return;
        if (level == levelSum.size()) {
            levelSum.add(root.val);
        } else {
            levelSum.set(level, levelSum.get(level) + root.val);
        }

        if (root.left != null) dfs(root.left, level +1);
        if (root.right != null) dfs(root.right, level + 1);
    }
}
